package arithmetic.demo4;




//class Solution {
//    public int maxProfit(int[] prices) {
//        int n = prices.length;
//        int[][] dp = new int[n][2];
//        dp[0][0] = -prices[0];
//        int count = 0;
//
//        for(int i = 1; i < n; i++) {
//            // 买入的状态
//            dp[i][0] = dp[i-1][0];
//
//            // 如果交易次数<2 就可以继续买入
//            if(count < 2) {
//                dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] - prices[i]);
//            }
//
//            // 卖出的状态
//            dp[i][1] = dp[i-1][1];
//
//            // 从买入到卖出就更新交易次数
//            if(dp[i-1][1] < dp[i-1][0] + prices[i]) {
//                dp[i][1] = dp[i-1][0] + prices[i];
//                count++;
//            }
//        }
//
//        return Math.max(dp[n-1][1],dp[n-1][0]);
//    }
//}


/**
 * 题目： dp_买卖股票的最大利润（三）
 */

class Solution1 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 创建 dp 表
        int[][] fp = new int[n][3];
        int[][] gp = new int[n][3];



        // 初始化
        fp[0][0] = -prices[0];
        for(int j = 1; j < 3; j++) {
            fp[0][j] = -0x3f3f3f3f;
        }



        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                // 买入的情况
                fp[i][j] = Math.max(fp[i-1][j], gp[i-1][j] - prices[i]);

                // 卖出的情况
                // 先更新不变的情况
                gp[i][j] =  gp[i-1][j];

                // 然后判断
                if(j - 1 >= 0) {
                    gp[i][j] = Math.max(gp[i-1][j], fp[i-1][j-1] + prices[i]);
                }

            }
        }

        int ret = -0x3f3f3f3f;

        // 寻找最大值
        for(int i = 0; i < 3; i++) {
            ret = Math.max(gp[n-1][i],ret);
        }

        return ret;
    }
}


//class Test {
//    public static void main(String[] args) {
//        int[]prices = new int[]{2,1,4,5,2,9,7};
//        Solution solution = new Solution();
//        System.out.println(solution.maxProfit(prices));
//    }
//}


/**
 * 题目： dp_买卖股票都最佳时机（四）
 */

class Solution2 {
    public int maxProfit(int k , int[] prices) {
        int n = prices.length;
        // 创建 dp 表
        int[][] fp = new int[n][k+1];
        int[][] gp = new int[n][k+1];


        // 初始化
        fp[0][0] = -prices[0];
        for(int j = 1; j < k+1; j++) {
            fp[0][j] = -0x3f3f3f3f;
        }



        for(int i = 1; i < n; i++) {
            for(int j = 0; j < k + 1; j++) {
                // 买入的情况
                fp[i][j] = Math.max(fp[i-1][j], gp[i-1][j] - prices[i]);

                // 卖出的情况
                // 先更新不变的情况
                gp[i][j] =  gp[i-1][j];

                // 然后判断
                if(j - 1 >= 0) {
                    gp[i][j] = Math.max(gp[i-1][j], fp[i-1][j-1] + prices[i]);
                }

            }
        }

        int ret = -0x3f3f3f3f;

        // 寻找最大值
        for(int i = 0; i < k+1; i++) {
            ret = Math.max(gp[n-1][i],ret);
        }

        return ret;
    }
}


/**
 * 题目： dp_最大数组和
 */

class Solution3 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        //  初始化
        // dp[0] = 0;


        //  开始进行动态规划
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }

        // 进行贪心
        int min = dp[0] , ret = -0x3f3f3f3f;
        for(int i = 1; i <= n;i++) {
            ret = Math.max(ret, dp[i] - min);
            min  = Math.min(dp[i], min);
        }

        return ret;
    }
}


/**
 * 题目： dp_最大数组和
 */

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        //  初始化
        // dp[0] = 0;


        //  开始进行动态规划
        for(int i = 1; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i-1]);
        }

        // 进行贪心
        int min = dp[0] , ret = -0x3f3f3f3f;
        for(int i = 1; i <= n;i++) {
            ret = Math.max(ret, dp[i] );
            // min  = Math.min(dp[i], min);
        }



        return ret;
    }
}


/**
 * 题目： 贪心_最大数组和
 */


class Solution4 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        //  初始化
        // dp[0] = 0;




        // 进行贪心
        int min = 0 , ret = -0x3f3f3f3f , sum  = 0;
        for(int i = 0; i < n;i++) {
            sum +=  nums[i];
            ret = Math.max(ret, sum - min);
            min  = Math.min(sum, min);
        }



        return ret;
    }
}


/**
 * 题目： dp_环形子数组最大和
 */

class Solution5 {

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] maxDp = new int[n + 1];
        int[] minDp = new int[n + 1];


        int ret = -0x3f3f3f3f;

        // 先计算总和
        int sum = 0;
        for(int i = 0; i < n; i++) {
            // 正难则反的思想
            sum += nums[i];
        }


        for(int i = 1; i <= n; i++) {
            // 最大值状态
            maxDp[i] = Math.max(maxDp[i - 1] + nums[i - 1], nums[i - 1] );
            // 最小值状态
            // 小贪心
            minDp[i] = Math.min(minDp[i - 1] + nums[i - 1], nums[i - 1] );

            // 更新
            ret = Math.max(ret, maxDp[i]);

            // 正难则反的思想
            if(i != n)
            ret = Math.max(ret, sum - minDp[i]);
        }


        return ret;

    }


}


class Test {
    public static void main(String[] args) {
//        Solution5 solution5 = new Solution5();
//        System.out.println(solution5.maxSubarraySumCircular(new int[]{-3, -2, -3}));

            Solution6 solution6 = new Solution6();
        System.out.println(solution6.maxProduct(new int[]{2, 3, -2, 4}));
    }
}

/**
 * 题目： dp_乘积最大子数组
 */


class Solution6 {
    public int maxProduct(int[] nums) {
        int least = 0x3f3f3f3f;
        int n = nums.length;
        int[] dpMax = new int[n+1];
        int[] dpMin = new int[n+1];
        int ret = -least;

        // 初始化
        dpMax[0] = dpMin[0] = 1;

        for(int i = 1; i<= n ; i++) {
            // 状态转移
            int max = -least, min = least;
            int num1 = nums[i-1] ,
                    num2 = dpMax[i-1] * nums[i-1] , num3 = dpMin[i-1] * nums[i-1];


            // 得到三个的最大值
            min = Math.min(min,num1);
            max = Math.max(max, num1);
            if(num1 >= 0 ) {
                max = Math.max(max, num2);
                min = Math.min(min,num3);

            } else {
                max = Math.max(max, num3);
                min = Math.min(min,num2);

            }
            // 最大值状态
            dpMax[i] = max;
            dpMin[i] = min;


            ret = Math.max(ret, dpMax[i]);
        }

        return ret;
    }
}


/**
 * 题目： dp_乘积为正数的最长子数组长度
 */

class Solution7 {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        // 创建 dp
        int[] fp = new int[n+1], gp = new int[n+1];

        // 初始化

        int ret  = -0x3f3f3f3f;
        // 状态转移
        for(int i = 1; i <= n; i++) {
            int num =  nums[i - 1];
            if(num  > 0) {
                // 正数状态
                fp[i] = fp[i - 1] + 1;
                // 负数 * 当前正数 = 负数
                // 先保证前面有负数
                gp[i] = gp[i -1] == 0 ? 0 : gp[i -1] + 1;;
            } else if(num < 0) {
                // 负数 *  负数 = 正数
                // 先判断前面有负数
                fp[i] = gp[i -1] == 0 ? 0 : gp[i -1] + 1;

                // 负数状态
                gp[i] = fp[i - 1] + 1;
            }

            ret = Math.max(ret, fp[i]);
        }


        return ret;
    }
}


/**
 * 题目： dp_等差数列划分
 */

class Solution8 {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(n < 3) return 0;
        // 创建dp
        int[] dp = new int[n+1];

        int ret = 0 ;
        // 填表
        for(int i = 3; i <= n; i++ ) {
            //   以i 位置为结尾的等差数列的个数
            if(nums[i-1] - nums[i-2] == nums[i-2] - nums[i-3]) {
                // 如果符合就继续加个数
                dp[i] = dp[i-1] + 1;
            } else {
                // 如果没有这个位置就为 0
                // 相当于把前面的等差数据给分隔开了
                dp[i] = 0;
            }

            ret += dp[i];
        }


        return ret;
    }
}